package org.gaaidou.ptarmigan.jdk.jvm;

import java.math.BigInteger;
import java.util.Random;

/**
 * Miller-Rabin primality test algorithm.
 */
public class PrimeGenerator {
    private static final int CERTAINTY = 100;

    public static BigInteger generate(int bitLength) {
        BigInteger prime;
        do {
            prime = new BigInteger(bitLength, new Random());
        } while (!isPrime(prime));
        return prime;
    }

    private static boolean isPrime(BigInteger n) {
        if (n.compareTo(BigInteger.ONE) <= 0) {
            return false;
        }
        if (n.compareTo(BigInteger.valueOf(3)) <= 0) {
            return true;
        }
        int s = 0;
        BigInteger d = n.subtract(BigInteger.ONE);
        while (d.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
            s++;
            d = d.divide(BigInteger.valueOf(2));
        }
        for (int i = 0; i < CERTAINTY; i++) {
            BigInteger a = randomBase(n);
            BigInteger x = a.modPow(d, n);
            if (x.equals(BigInteger.ONE) || x.equals(n.subtract(BigInteger.ONE))) {
                continue;
            }
            boolean isPrime = false;
            for (int j = 0; j < s - 1; j++) {
                x = x.modPow(BigInteger.valueOf(2), n);
                if (x.equals(n.subtract(BigInteger.ONE))) {
                    isPrime = true;
                    break;
                }
            }
            if (!isPrime) {
                return false;
            }
        }
        return true;
    }

    private static BigInteger randomBase(BigInteger n) {
        Random rand = new Random();
        BigInteger a;
        do {
            a = new BigInteger(n.bitLength(), rand);
        } while (a.compareTo(BigInteger.ONE) <= 0 || a.compareTo(n.subtract(BigInteger.ONE)) >= 0);
        return a;
    }
}